/**
 * 
 */
package bitManipulation;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].
 */
public class RepeatedDNASequences {

	/*
	 * Pure hashtable
	 * ERROR: Memory Limit Exceeded
	 */
    public List<String> findRepeatedDnaSequencesHashOnly(String s) {
    	final Set<String> onceWords = new HashSet<>();
    	final Set<String> twiceWords = new HashSet<>();
    	final List<String> result = new LinkedList<>();
    	
    	for (int i = 0, size = s.length() - 10; i <= size; i++) {
    		String word = s.substring(i, i + 10);
    		if (!onceWords.add(word) && twiceWords.add(word)) {
    			result.add(word);
    		}
    	}
    	
        return result;
    }
    
    public List<String> findRepeatedDnaSequencesHashBit(String s) {
    	final Set<Integer> onceWords = new HashSet<>();
    	final Set<Integer> twiceWords = new HashSet<>();
    	final List<String> result = new LinkedList<>();
    	final int[] map = new int[26];
    	map['A' - 'A'] = 0;
    	map['C' - 'A'] = 1;
    	map['G' - 'A'] = 2;
    	map['T' - 'A'] = 3;
    	
    	for (int i = 0, sizeI = s.length() - 9; i < sizeI; i++) {
    		int value = 0;
    		for (int j = i, sizeJ = i + 10; j < sizeJ; j++) {
    			value = value << 2;
    			value = value | map[s.charAt(j) - 'A'];
    		}
    		if (!onceWords.add(value) && twiceWords.add(value)) {
    			result.add(s.substring(i, i + 10));
    		}
    	}
    	
        return result;
    }
	
	
	public RepeatedDNASequences() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
